{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Even Odd Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isEvenOddTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #奇偶树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>如果一棵二叉树满足下述几个条件，则可以称为 <strong>奇偶树</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>二叉树根节点所在层下标为 <code>0</code> ，根的子节点所在层下标为 <code>1</code> ，根的孙节点所在层下标为 <code>2</code> ，依此类推。</li>\n",
    "\t<li><strong>偶数下标</strong> 层上的所有节点的值都是 <strong>奇</strong> 整数，从左到右按顺序 <strong>严格递增</strong></li>\n",
    "\t<li><strong>奇数下标</strong> 层上的所有节点的值都是 <strong>偶</strong> 整数，从左到右按顺序 <strong>严格递减</strong></li>\n",
    "</ul>\n",
    "\n",
    "<p>给你二叉树的根节点，如果二叉树为 <strong>奇偶树 </strong>，则返回 <code>true</code> ，否则返回 <code>false</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/04/sample_1_1966.png\" style=\"height: 229px; width: 362px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,10,4,3,null,7,9,12,8,6,null,null,2]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>每一层的节点值分别是：\n",
    "0 层：[1]\n",
    "1 层：[10,4]\n",
    "2 层：[3,7,9]\n",
    "3 层：[12,8,6,2]\n",
    "由于 0 层和 2 层上的节点值都是奇数且严格递增，而 1 层和 3 层上的节点值都是偶数且严格递减，因此这是一棵奇偶树。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/04/sample_2_1966.png\" style=\"height: 167px; width: 363px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [5,4,2,3,3,7]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>每一层的节点值分别是：\n",
    "0 层：[5]\n",
    "1 层：[4,2]\n",
    "2 层：[3,3,7]\n",
    "2 层上的节点值不满足严格递增的条件，所以这不是一棵奇偶树。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/04/sample_1_333_1966.png\" style=\"height: 167px; width: 363px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [5,9,1,3,5,7]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>1 层上的节点值应为偶数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1]\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [11,8,6,1,3,9,11,30,20,18,16,12,10,4,2,17]\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数在范围 <code>[1, 10<sup>5</sup>]</code> 内</li>\n",
    "\t<li><code>1 <= Node.val <= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [even-odd-tree](https://leetcode.cn/problems/even-odd-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [even-odd-tree](https://leetcode.cn/problems/even-odd-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,10,4,3,null,7,9,12,8,6,null,null,2]', '[5,4,2,3,3,7]', '[5,9,1,3,5,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        q = deque()\n",
    "        q.append(root)\n",
    "        even = True\n",
    "        while q:\n",
    "            sz = len(q)\n",
    "            prev = None\n",
    "            for i in range(sz):\n",
    "                curr = q.popleft()\n",
    "                if even:\n",
    "                    if curr.val%2 == 0:\n",
    "                        return False\n",
    "                    if prev and prev.val >= curr.val:\n",
    "                        return False\n",
    "                if not even:\n",
    "                    if curr.val %2 == 1:\n",
    "                        return False\n",
    "                    if prev and prev.val <= curr.val:\n",
    "                        return False\n",
    "                if curr.left:\n",
    "                    q.append(curr.left)\n",
    "                if curr.right:\n",
    "                    q.append(curr.right)\n",
    "                prev = curr\n",
    "            even = not even\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        q = deque()\n",
    "        q.append(root)\n",
    "        level = 0\n",
    "        while q:\n",
    "            t = deque()\n",
    "            last = None\n",
    "            while q:\n",
    "                front = q.popleft()\n",
    "                val = front.val\n",
    "                if level % 2 == 0:\n",
    "                    if val % 2 != 1 or (last and val <= last):\n",
    "                        return False\n",
    "                else:\n",
    "                    if val % 2 != 0 or (last and val >= last):\n",
    "                        return False\n",
    "                last = val\n",
    "                if front.left:\n",
    "                    t.append(front.left)\n",
    "                if front.right:\n",
    "                    t.append(front.right)\n",
    "            q = t\n",
    "            level += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        qu = [root]\n",
    "        is_even = True\n",
    "        while qu:\n",
    "            size = len(qu)\n",
    "            pre = inf\n",
    "            for _ in range(size):\n",
    "                x = qu[0].val\n",
    "                node = qu[0]\n",
    "                if is_even:\n",
    "                    x = -x\n",
    "                if (x % 2 == 1) != is_even or x >= pre:\n",
    "                    print(x)\n",
    "                    print(is_even)\n",
    "                    return False\n",
    "                pre = x\n",
    "                if node.left:\n",
    "                    qu.append(node.left)\n",
    "                if node.right:\n",
    "                    qu.append(node.right)\n",
    "\n",
    "                del qu[0]\n",
    "\n",
    "            is_even = not is_even\n",
    "        \n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        q = [root]\n",
    "        cnt = 0\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            n = len(tmp)\n",
    "            for i in range(n):\n",
    "                if tmp[i].left:\n",
    "                    q.append(tmp[i].left)\n",
    "                if tmp[i].right:\n",
    "                    q.append(tmp[i].right)\n",
    "                if cnt%2 == 0:\n",
    "                    if tmp[i].val%2 == 0:\n",
    "                        return False\n",
    "                    if i != 0 and tmp[i].val <= tmp[i-1].val:\n",
    "                        return False\n",
    "                else:\n",
    "                    if tmp[i].val%2 == 1:\n",
    "                        return False\n",
    "                    if i != 0 and tmp[i].val >= tmp[i-1].val:\n",
    "                        return False\n",
    "            cnt += 1\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        level, nodes  = 0, [root]\n",
    "        while nodes:\n",
    "            nxt, cur = [], inf if level % 2 else 0\n",
    "            for node in nodes:\n",
    "                if (level % 2 == node.val % 2) or (level % 2 and cur <= node.val) or (not (level % 2) and cur >= node.val):\n",
    "                    return False\n",
    "                cur = node.val\n",
    "                if node.left:\n",
    "                    nxt.append(node.left)\n",
    "                if node.right:\n",
    "                    nxt.append(node.right)\n",
    "            nodes = nxt\n",
    "            level += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        level = 0\n",
    "        q = [root]\n",
    "        if root.val % 2 == 0:\n",
    "            return False\n",
    "        while q:\n",
    "            new_q = []\n",
    "            level += 1\n",
    "            for x in q:\n",
    "                if x.left:\n",
    "                    if (level % 2 != 0 and x.left.val % 2 != 0) or (level % 2 == 0 and x.left.val % 2 == 0):\n",
    "                        return False\n",
    "                    if new_q:\n",
    "                        if (level % 2 != 0 and x.left.val >= new_q[-1].val) or (level % 2 == 0 and x.left.val <= new_q[-1].val):\n",
    "                            return False\n",
    "                    new_q.append(x.left)\n",
    "                if x.right:\n",
    "                    if (level % 2 != 0 and x.right.val % 2 != 0) or (level % 2 == 0 and x.right.val % 2 == 0):\n",
    "                        return False\n",
    "                    if new_q:\n",
    "                        if (level % 2 != 0 and x.right.val >= new_q[-1].val) or (level % 2 == 0 and x.right.val <= new_q[-1].val):\n",
    "                            return False\n",
    "                    new_q.append(x.right)\n",
    "            q = new_q\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        q = deque([root])\n",
    "        odd = True\n",
    "        def check():\n",
    "            if odd:\n",
    "                if node.val % 2 != 1:\n",
    "                    return False\n",
    "                if pre and pre.val >= node.val:\n",
    "                    return False\n",
    "            else:\n",
    "                if node.val % 2 != 0:\n",
    "                    return False\n",
    "                if pre and pre.val <= node.val:\n",
    "                    return False\n",
    "            return True\n",
    "        while q:\n",
    "            pre = None\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if not check(): return False\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "                pre = node\n",
    "            odd = not odd\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # bfs\n",
    "        q = deque(((root, 0),))\n",
    "        last_val = 0\n",
    "        last_level = 0\n",
    "        while q:\n",
    "            node, level = q.popleft()\n",
    "            val = node.val\n",
    "            if not (level & 1) ^ (val & 1):\n",
    "                return False\n",
    "            if level == last_level:\n",
    "                if val == last_val:\n",
    "                    return False\n",
    "                if (level & 1) ^ (val < last_val):\n",
    "                    return False\n",
    "            else:\n",
    "                last_level = level\n",
    "            last_val = val\n",
    "            if node.left:\n",
    "                q.append((node.left, level + 1))\n",
    "            if node.right:\n",
    "                q.append((node.right, level + 1))\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        q = [root]\n",
    "        level = 0\n",
    "        while q:\n",
    "            pre = inf if level & 1 else 0\n",
    "            nxt = []\n",
    "            for node in q:\n",
    "                v = node.val\n",
    "                if v % 2 == level % 2 or level % 2 == 0 and v <= pre or level & 1 and v >= pre:\n",
    "                    return False\n",
    "                pre = v\n",
    "                if node.left:\n",
    "                    nxt.append(node.left)\n",
    "                if node.right:\n",
    "                    nxt.append(node.right)\n",
    "            q = nxt\n",
    "            level += 1\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        queue=[root]\n",
    "        level=1\n",
    "        while(queue):\n",
    "            # print(queue,'level:',level)\n",
    "            next_queue=[]\n",
    "            for i,q in enumerate(queue):\n",
    "                if q==None:\n",
    "                    continue\n",
    "                if level==2 :\n",
    "                    if q.val%2!=0 or (i>0 and q.val>=queue[i-1].val):\n",
    "                        return False\n",
    "                elif level==1:\n",
    "                    if q.val%2==0 or(i>0 and q.val<=queue[i-1].val):\n",
    "                        return False\n",
    "                if q.left!=None:\n",
    "                    next_queue.append(q.left)\n",
    "                if q.right!=None:\n",
    "                    next_queue.append(q.right)\n",
    "            level=1 if level==2 else 2\n",
    "            queue=next_queue\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root :\n",
    "            return True\n",
    "        if root.val % 2==0:\n",
    "            return False\n",
    "        queue=[root]\n",
    "        result=0\n",
    "        level=1\n",
    "        while queue:\n",
    "            temp=[]\n",
    "            level*=-1\n",
    "            temp_var=-inf\n",
    "            for q in queue:\n",
    "                if q.left:\n",
    "                    if q.left.val*level<=temp_var or q.left.val % 2==(-0.5*level+0.5):\n",
    "                        return False\n",
    "                    temp_var=q.left.val*level\n",
    "                    temp.append(q.left)\n",
    "                if q.right:\n",
    "                    if q.right.val*level<=temp_var or q.right.val % 2==(-0.5*level+0.5):\n",
    "                        return False\n",
    "                    temp_var=q.right.val*level\n",
    "                    temp.append(q.right)\n",
    "            queue=temp\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        t=0\n",
    "        v=[root]\n",
    "        while v:\n",
    "            l=[]\n",
    "            arr=[]\n",
    "            for x in v:\n",
    "                arr.append(x.val)\n",
    "                if x.left:\n",
    "                    l.append(x.left)\n",
    "                if x.right:\n",
    "                    l.append(x.right)\n",
    "\n",
    "            for i in range(len(arr)):\n",
    "                if t&1:\n",
    "                    if arr[i]&1:\n",
    "                        return False\n",
    "                    if i>0 and arr[i]>=arr[i-1]:\n",
    "                        return False\n",
    "                else:\n",
    "                    if arr[i]&1==0:\n",
    "                        return False\n",
    "                    if i>0 and arr[i]<=arr[i-1]:\n",
    "                        return False\n",
    "            t+=1\n",
    "            v=l \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # 层序遍历\n",
    "        now_level = 0 # 当前的层数\n",
    "        q=[root] # 初始化当前的层有的元素\n",
    "        while len(q)>0:\n",
    "            # 遍历这一层的所有元素，先将这一层搬空\n",
    "            temp_node = q.copy()\n",
    "            q = []\n",
    "            \n",
    "            pre_num=None # 记录这一层是递增还是递减\n",
    "            for node in temp_node:\n",
    "                if now_level%2==0:\n",
    "                    # 当前是偶数层\n",
    "                    # 需要所有节点的值为奇数\n",
    "                    if node.val%2!=1:\n",
    "                        return False\n",
    "                    # 还需要递增\n",
    "                    if pre_num==None:\n",
    "                        pre_num=node.val\n",
    "                    else:\n",
    "                        if node.val<=pre_num:\n",
    "                            return False\n",
    "                else:\n",
    "                    # 当前是奇数层\n",
    "                    # 需要所有节点的值为偶数\n",
    "                    if node.val%2!=0:\n",
    "                        return False\n",
    "                    # 还需要递减少\n",
    "                    if pre_num==None:\n",
    "                        pre_num=node.val\n",
    "                    else:\n",
    "                        if node.val>=pre_num:\n",
    "                            return False\n",
    "                # 更新这个节点的值，用于下次递增递减的判断\n",
    "                pre_num = node.val\n",
    "                # 如果不为空将节点的左右子树加入队列\n",
    "                if node.left!=None:\n",
    "                    q.append(node.left)\n",
    "                if node.right!=None:\n",
    "                    q.append(node.right)\n",
    "            # 层数加1，用于判断奇数偶数层\n",
    "            now_level+=1\n",
    "        # 所有的都遍历完，说明都符合要求，返回True\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # bfs\n",
    "        q = deque(((root, 0),))\n",
    "        last_val = 0\n",
    "        last_level = 0\n",
    "        while q:\n",
    "            node, level = q.popleft()\n",
    "            val = node.val\n",
    "            if not (level & 1) ^ (val & 1):\n",
    "                return False\n",
    "            if level == last_level:\n",
    "                if val == last_val:\n",
    "                    return False\n",
    "                if (level & 1) ^ (val < last_val):\n",
    "                    return False\n",
    "            else:\n",
    "                last_level = level\n",
    "            last_val = val\n",
    "            if node.left:\n",
    "                q.append((node.left, level + 1))\n",
    "            if node.right:\n",
    "                q.append((node.right, level + 1))\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        queue = [root]\n",
    "        odd = False\n",
    "        while queue:\n",
    "            nxt = []\n",
    "            for i in range(len(queue)):\n",
    "                if odd:\n",
    "                    if i == 0 and queue[i].val % 2 == 1: \n",
    "                        return False\n",
    "                    elif i > 0:\n",
    "                        if queue[i].val % 2 == 1 or queue[i].val >= queue[i-1].val: return False\n",
    "                else:\n",
    "                    if i == 0 and queue[i].val % 2 == 0: \n",
    "                        return False\n",
    "                    elif i > 0:\n",
    "                        if queue[i].val % 2 == 0 or queue[i].val <= queue[i-1].val: return False\n",
    "                if queue[i].left: nxt.append(queue[i].left)\n",
    "                if queue[i].right: nxt.append(queue[i].right)\n",
    "            queue = nxt \n",
    "            odd = not odd \n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        flag = True\n",
    "        path = [root]\n",
    "        while path:\n",
    "            for i in range(len(path)-1):\n",
    "                if flag and path[i].val >= path[i+1].val or not flag and path[i].val <= path[i+1].val:return False\n",
    "            for node in path:\n",
    "                if flag^(node.val % 2 == 1):return False\n",
    "            flag ^= True\n",
    "            to_path = []\n",
    "            for node in path:\n",
    "                if node.left:to_path.append(node.left)\n",
    "                if node.right:to_path.append(node.right)\n",
    "            path = to_path\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        q= deque([root])\n",
    "        flag = False\n",
    "        while q:\n",
    "            if not flag:\n",
    "                val = -inf\n",
    "            else:\n",
    "                val = inf\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                x = node.val\n",
    "                if not flag and (x <= val or x%2 == 0):\n",
    "                    return False\n",
    "                if  flag and (x >= val or x%2 == 1):\n",
    "                    return False\n",
    "                val = x\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right:q.append(node.right)\n",
    "            flag = not flag\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "\n",
    "        queue =  [root]\n",
    "        level = 0\n",
    "        while queue:\n",
    "\n",
    "            prev = float('inf') if level%2 else 0\n",
    "            nxt = []\n",
    "            for node in queue:\n",
    "                val = node.val\n",
    "                if val%2 ==level%2 or (level%2==0 and val<=prev) or (level%2==1 and val>=prev):\n",
    "                    return False\n",
    "                prev = val\n",
    "                if node.left:\n",
    "                    nxt.append(node.left)\n",
    "                if node.right:\n",
    "                    nxt.append(node.right)\n",
    "                \n",
    "\n",
    "            queue = nxt\n",
    "            level +=1\n",
    "        return True\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        q = deque([root])\n",
    "        layer = True\n",
    "        while q:\n",
    "            pre_even = -inf\n",
    "            pre_odd = inf\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if layer:\n",
    "                    if node.val <= pre_even or node.val % 2 == 0:\n",
    "                        return False\n",
    "                else:\n",
    "                    if node.val >= pre_odd or node.val % 2 != 0:\n",
    "                        return False\n",
    "\n",
    "                pre_odd = pre_even = node.val\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            layer = not layer\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root is None:\n",
    "            return  True\n",
    "\n",
    "        q = collections.deque()\n",
    "        q.append(root)\n",
    "        \n",
    "        even = True\n",
    "        while q:\n",
    "            sz = len(q)\n",
    "            prev = float('-inf') if even else float('inf')\n",
    "            for i in range(sz):\n",
    "                cur = q.popleft()\n",
    "                if even:\n",
    "                    if prev >= cur.val or cur.val % 2 == 0:\n",
    "                        return False\n",
    "                else:\n",
    "                    if prev <= cur.val or cur.val % 2 == 1:\n",
    "                        return False\n",
    "                prev = cur.val\n",
    "                if cur.left:\n",
    "                    q.append(cur.left)\n",
    "                if cur.right:\n",
    "                    q.append(cur.right)\n",
    "            even = not even\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        q = deque([root])\n",
    "        p = deque([])\n",
    "        if root.val % 2 == 0:\n",
    "            return False\n",
    "        i = 0\n",
    "        while len(q) != 0:\n",
    "            even = float('inf')\n",
    "            odd = float('-inf')\n",
    "            while len(q) != 0:\n",
    "                node = q.popleft()\n",
    "                val = node.val\n",
    "                print(val, i)\n",
    "                if i  % 2 == 0:\n",
    "                    if val % 2 == 0:\n",
    "                        return False\n",
    "                    if val <= odd:\n",
    "                        return False\n",
    "                    odd = val\n",
    "                if i % 2 == 1:\n",
    "                    if val % 2 == 1:\n",
    "                        return False\n",
    "                    if val >= even:\n",
    "                        return False\n",
    "                    even = val\n",
    "\n",
    "                if node.left is not None:\n",
    "                    p.append(node.left)\n",
    "                if node.right is not None:\n",
    "                    p.append(node.right)\n",
    "\n",
    "            i += 1\n",
    "                \n",
    "            p, q = q, p\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        q = deque([root])\n",
    "        odd = True\n",
    "        while q:\n",
    "            pre = -inf if odd else inf\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if odd is not (node.val % 2 == 1):\n",
    "                    return False\n",
    "                if not (odd and pre < node.val or not odd and pre > node.val):\n",
    "                    return False\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "                pre = node.val\n",
    "            odd = not odd\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # bfs\n",
    "        q = deque(((root, 0),))\n",
    "        last_val = 0\n",
    "        last_level = 0\n",
    "        while q:\n",
    "            node, level = q.popleft()\n",
    "            val = node.val\n",
    "            if not (level & 1) ^ (val & 1):\n",
    "                return False\n",
    "            if level == last_level:\n",
    "                if level & 1:\n",
    "                    if val >= last_val:\n",
    "                        return False\n",
    "                elif val <= last_val:\n",
    "                    return False\n",
    "            else:\n",
    "                last_level = level\n",
    "            last_val = val\n",
    "            if node.left:\n",
    "                q.append((node.left, level + 1))\n",
    "            if node.right:\n",
    "                q.append((node.right, level + 1))\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        queue = [root]\n",
    "        level = 0\n",
    "        while queue:\n",
    "            res = []\n",
    "            for a in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                res.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            if self.is_sorted(res, level % 2 == 0):\n",
    "                level += 1\n",
    "                continue\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def is_sorted(self, res, asc):\n",
    "        r = 0 if asc else float('inf')\n",
    "        for a in res:\n",
    "            if asc:\n",
    "                if r < a and a % 2 != 0:\n",
    "                    r = a\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if r > a and a % 2 == 0:\n",
    "                    r = a\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        level, nodes = 0, [root]\n",
    "        while nodes:\n",
    "            nxt, cur = [], inf if level % 2 else 0\n",
    "            for node in nodes:\n",
    "                if (node.val % 2 == level % 2) or (level % 2 and cur <= node.val) or ((not level % 2) and cur >= node.val):\n",
    "                    return False\n",
    "                cur = node.val\n",
    "                if node.left:\n",
    "                    nxt.append(node.left)\n",
    "                if node.right:\n",
    "                    nxt.append(node.right)\n",
    "            nodes = nxt\n",
    "            level += 1\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        even=True\n",
    "        q=deque([root])\n",
    "        while q:\n",
    "            if even:\n",
    "                temp=-inf\n",
    "            if not even:\n",
    "                temp=inf\n",
    "            for i in range(len(q)):\n",
    "                node=q.popleft()\n",
    "                if even:\n",
    "                    if node.val %2 == 0 or node.val<=temp:\n",
    "                        return False\n",
    "                if not even:\n",
    "                    if node.val %2 != 0 or node.val>=temp:\n",
    "                        return False\n",
    "                temp=node.val\n",
    "                if node.left:q.append(node.left)\n",
    "                if node.right:q.append(node.right)\n",
    "            even=not even\n",
    "        return True\n",
    "\n",
    "                \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # bfs\n",
    "        q = deque(((root, 0),))\n",
    "        last_val = 0\n",
    "        last_level = 0\n",
    "        while q:\n",
    "            node, level = q.popleft()\n",
    "            val = node.val\n",
    "            if not (level & 1) ^ (val & 1):\n",
    "                return False\n",
    "            if level == last_level:\n",
    "                if val == last_val or (level & 1) ^ (val < last_val):\n",
    "                    return False\n",
    "            else:\n",
    "                last_level = level\n",
    "            last_val = val\n",
    "            if node.left:\n",
    "                q.append((node.left, level + 1))\n",
    "            if node.right:\n",
    "                q.append((node.right, level + 1))\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        q = collections.deque([root])\n",
    "        single = True\n",
    "        while q:\n",
    "            pre = 0 if single else 10**6+1 \n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if node.val % 2 != single:\n",
    "                    return False\n",
    "                if single:\n",
    "                    if node.val <= pre:\n",
    "                        return False\n",
    "                    else:\n",
    "                        pre = node.val\n",
    "                else:\n",
    "                    if node.val >= pre:\n",
    "                        return False\n",
    "                    else:\n",
    "                        pre = node.val\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "\n",
    "            single = not single\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        q=deque([root])\n",
    "        even_level=True\n",
    "        while q:\n",
    "            pre=-1 if even_level else inf\n",
    "            for i in range(len(q)):\n",
    "                node=q.popleft()\n",
    "                if even_level:\n",
    "                    if node.val % 2 ==0 or node.val<=pre:\n",
    "                        return False\n",
    "                else:\n",
    "                    if node.val % 2 ==1 or node.val>=pre:\n",
    "                        return False\n",
    "                pre=node.val\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            even_level= not even_level\n",
    "        return True\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def judge(nums,deep):\n",
    "            if deep%2==0:\n",
    "                for i in range(len(nums)):\n",
    "                    if nums[i]%2==0:\n",
    "                        return False\n",
    "                    if i<len(nums)-1 and nums[i]>=nums[i+1]:\n",
    "                        return False\n",
    "            else:\n",
    "                for i in range(len(nums)):\n",
    "                    if nums[i]%2==1:\n",
    "                        return False\n",
    "                    if i<len(nums)-1 and nums[i]<=nums[i+1]:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        if not root:\n",
    "            return False\n",
    "        dq=deque([root])\n",
    "        deep=0\n",
    "        while dq:\n",
    "            qsize=len(dq)\n",
    "            level=[]\n",
    "            for _ in range(qsize):\n",
    "                node=dq.popleft()\n",
    "                level.append(node.val)\n",
    "                if node.left:\n",
    "                    dq.append(node.left)\n",
    "                if node.right:\n",
    "                    dq.append(node.right)\n",
    "            if not judge(level,deep):\n",
    "                return False\n",
    "            deep+=1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        h = [root]\n",
    "        f = 1\n",
    "        while len(h)>0:\n",
    "            s = []\n",
    "            p = -1 if f else 10**6+5\n",
    "            for v in h:\n",
    "                if v.val&1!=f:\n",
    "                    return False\n",
    "                if (f and p >= v.val) or (not f and p <= v.val):\n",
    "                    return False\n",
    "                p = v.val\n",
    "                if v.left:\n",
    "                    s.append(v.left)\n",
    "                if v.right:\n",
    "                    s.append(v.right)\n",
    "            h = s\n",
    "            f ^= 1\n",
    "        return True\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # bfs\n",
    "        q = deque(((root, 0),))\n",
    "        last_val = 0\n",
    "        last_level = 0\n",
    "        while q:\n",
    "            node, level = q.popleft()\n",
    "            val = node.val\n",
    "            if (level & 1) == (val & 1):\n",
    "                return False\n",
    "            if level == last_level:\n",
    "                if val == last_val:\n",
    "                    return False\n",
    "                if (level & 1) ^ (val < last_val):\n",
    "                    return False\n",
    "            else:\n",
    "                last_level = level\n",
    "            last_val = val\n",
    "            if node.left:\n",
    "                q.append((node.left, level + 1))\n",
    "            if node.right:\n",
    "                q.append((node.right, level + 1))\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "from itertools import pairwise\n",
    "class Solution(object):\n",
    "    def isEvenOddTree(self, root):\n",
    "        index = 0\n",
    "        d = deque([root])\n",
    "        if root.val%2==0:\n",
    "            return False\n",
    "        while d:\n",
    "            sz = len(d)\n",
    "            flag = index % 2 == 0\n",
    "            if flag:\n",
    "                if len(d)==1 and d[0].val%2==0:\n",
    "                    return False\n",
    "                else:\n",
    "                    for a,b in pairwise(d):\n",
    "                        if a.val>=b.val or a.val%2==0 or b.val%2==0:\n",
    "                            return False\n",
    "            if not flag:\n",
    "                if len(d)==1 and d[0].val%2==1:\n",
    "                    return False\n",
    "                else:\n",
    "                    for a,b in pairwise(d):\n",
    "                        if a.val<=b.val or a.val%2==1 or b.val%2==1:\n",
    "                            return False\n",
    "            for _ in range(sz):\n",
    "                curr = d.popleft()\n",
    "                if curr.left:\n",
    "                    d.append(curr.left)\n",
    "                if curr.right:\n",
    "                    d.append(curr.right)\n",
    "            index += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        q = deque()\n",
    "        q.append(root)\n",
    "        f1 = 1  # 奇偶层标志\n",
    "        f2 = 1  # 递增递减标志\n",
    "        while q:\n",
    "            pre = -1\n",
    "            sz = len(q)\n",
    "            for _ in range(sz):\n",
    "                cur = q.popleft()\n",
    "                if cur.val & 1 == f1 and (pre == -1 or f2*cur.val > pre*f2):\n",
    "                    pre = cur.val\n",
    "                else:\n",
    "                    return False\n",
    "                if cur.left:\n",
    "                    q.append(cur.left)\n",
    "                if cur.right:\n",
    "                    q.append(cur.right)\n",
    "            f1 ^= 1\n",
    "            f2 *= -1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "\n",
    "        q = collections.deque([root])\n",
    "        depth = 0\n",
    "        \n",
    "        while q:\n",
    "            size = len(q)\n",
    "            if depth % 2 == 0:  # For even level\n",
    "                prev_val = -1  # Start with a small value\n",
    "            else:  # For odd level\n",
    "                prev_val = float('inf')  # Start with a big value\n",
    "            \n",
    "            for i in range(size):\n",
    "                node = q.popleft()\n",
    "                if depth % 2 == 0:\n",
    "                    # Check the current value should be odd and strictly increasing\n",
    "                    if node.val % 2 == 0 or node.val <= prev_val:\n",
    "                        return False\n",
    "                else:\n",
    "                    # Check the current value should be even and strictly decreasing\n",
    "                    if node.val % 2 != 0 or node.val >= prev_val:\n",
    "                        return False\n",
    "                        \n",
    "                prev_val = node.val  # Update the previous value\n",
    "                \n",
    "                for child in [node.left, node.right]:\n",
    "                    if child:\n",
    "                        q.append(child)\n",
    "            \n",
    "            depth += 1\n",
    "            \n",
    "        return True\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        queue = [root]\n",
    "        level = 0\n",
    "        while queue:\n",
    "            prev = float('inf') if level % 2 else 0\n",
    "            nxt = []\n",
    "            for node in queue:\n",
    "                val = node.val\n",
    "                if val % 2 == level % 2 or level % 2 == 0 and val <= prev or level % 2 == 1 and val >= prev:\n",
    "                    return False\n",
    "                prev = val\n",
    "                if node.left:\n",
    "                    nxt.append(node.left)\n",
    "                if node.right:\n",
    "                    nxt.append(node.right)\n",
    "            queue = nxt\n",
    "            level += 1\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        stack, deep = [root], 0\n",
    "        while len(stack):\n",
    "            temp = list()\n",
    "            pre = 1000001 if deep % 2 else 0\n",
    "            for node in stack:\n",
    "                if deep % 2 == 0: # 奇数，且严格递增\n",
    "                    if (node.val <= pre) or (node.val % 2 != 1):\n",
    "                        return False\n",
    "                else:\n",
    "                    if (node.val >= pre) or (node.val % 2 != 0):\n",
    "                        return False\n",
    "                pre = node.val\n",
    "                if node.left:\n",
    "                    temp.append(node.left)\n",
    "                if node.right:\n",
    "                    temp.append(node.right)\n",
    "            deep += 1\n",
    "            stack = temp\n",
    "        return True\n",
    "                \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        q, even = deque([root]), True\n",
    "        while q:\n",
    "            level = []\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                level.append(node.val)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            if even and (any(n % 2 == 0 for n in level) or level != sorted(level)) :\n",
    "                return False\n",
    "            if not even and (any(n % 2 == 1 for n in level) or level != sorted(level, reverse = True)):\n",
    "                return False\n",
    "            if len(level) != len(set(level)):\n",
    "                return False\n",
    "            even = not even\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        queue = [root]\n",
    "        level = 0\n",
    "        while queue:\n",
    "            res = []\n",
    "            for a in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                res.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            print(res, level)\n",
    "            if self.is_sorted(res, level % 2 == 0):\n",
    "                level += 1\n",
    "                continue\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def is_sorted(self, res, asc):\n",
    "        r = 0 if asc else float('inf')\n",
    "        for a in res:\n",
    "            if asc:\n",
    "                if r < a and a % 2 != 0:\n",
    "                    r = a\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if r > a and a % 2 == 0:\n",
    "                    r = a\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        q = collections.deque([root])\n",
    "        even = 1\n",
    "        while q:\n",
    "            n = len(q)\n",
    "            for i in range(n):\n",
    "                node = q.popleft()     \n",
    "                if i < n-1:\n",
    "                    if even:\n",
    "                        if node.val % 2 == 0 or node.val >= q[0].val:\n",
    "                            return False\n",
    "                    else:\n",
    "                        if node.val % 2 != 0 or node.val <= q[0].val:\n",
    "                            return False\n",
    "                else:\n",
    "                    if even:\n",
    "                        if node.val % 2 == 0: \n",
    "                            return False\n",
    "                    else:\n",
    "                        if node.val % 2 != 0:\n",
    "                            return False\n",
    "                if node.left:q.append(node.left)\n",
    "                if node.right:q.append(node.right)\n",
    "            even = not even    \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        q = collections.deque([root])\n",
    "        ou = True\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            while size > 0:\n",
    "                node = q.popleft()\n",
    "                size -= 1\n",
    "                if ou:\n",
    "                    if node.val % 2 == 0:\n",
    "                        return False\n",
    "                    if size>0:\n",
    "                        if node.val >= q[0].val:\n",
    "                            return False\n",
    "                else:\n",
    "                    if node.val % 2 == 1:\n",
    "                        return False\n",
    "                    if size>0:\n",
    "                        if node.val <= q[0].val:\n",
    "                            return False\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            ou = not ou\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        queue = [root]\n",
    "        level = 0\n",
    "        while queue:\n",
    "            prev = float('inf') if level % 2 == 1 else 0\n",
    "            nxt = []\n",
    "            for node in queue:\n",
    "                val = node.val\n",
    "                if val % 2 == level % 2 or level % 2 == 0 and val <= prev or level % 2 == 1 and val >= prev:\n",
    "                    return False\n",
    "                prev = val\n",
    "                if node.left:\n",
    "                    nxt.append(node.left)\n",
    "                if node.right:\n",
    "                    nxt.append(node.right)\n",
    "            queue = nxt\n",
    "            level += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "\n",
    "        q = collections.deque()\n",
    "        q.append(root)\n",
    "        # 记录奇偶层数\n",
    "        even = True\n",
    "        # while 循环控制从上向下一层层遍历\n",
    "        while q:\n",
    "            sz = len(q)\n",
    "            # 记录前一个节点，便于判断是否递增/递减\n",
    "            prev = float('-inf') if even else float('inf')\n",
    "            # for 循环控制每一层从左向右遍历\n",
    "            for i in range(sz):\n",
    "                cur = q.popleft()\n",
    "                if even:\n",
    "                    # 偶数层\n",
    "                    if prev >= cur.val or cur.val % 2 == 0:\n",
    "                        return False\n",
    "                else:\n",
    "                    # 奇数层\n",
    "                    if prev <= cur.val or cur.val % 2 == 1:\n",
    "                        return False\n",
    "                prev = cur.val\n",
    "\n",
    "                if cur.left:\n",
    "                    q.append(cur.left)\n",
    "                if cur.right:\n",
    "                    q.append(cur.right)\n",
    "            # 奇偶层数切换\n",
    "            even = not even\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        queue = [root]\n",
    "        level = 0\n",
    "        while queue:\n",
    "            prev = float('inf') if level % 2 else 0\n",
    "            nxt = []\n",
    "            for node in queue:\n",
    "                val = node.val\n",
    "                if val & 1 == level & 1 or not level & 1 and val <= prev or level & 1 and val >= prev:\n",
    "                    return False\n",
    "                prev = val\n",
    "                if node.left:\n",
    "                    nxt.append(node.left)\n",
    "                if node.right:\n",
    "                    nxt.append(node.right)\n",
    "            queue = nxt\n",
    "            level += 1\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        level = 0\n",
    "        q = [root]\n",
    "        def check(nums, level):\n",
    "            if len(nums) == 1:\n",
    "                if level%2 == 0 and nums[0]%2 !=0:\n",
    "                    return True\n",
    "                elif level%2 != 0 and nums[0]%2 ==0:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            if level%2 == 0:\n",
    "                if nums[0]%2 == 0:\n",
    "                    return False\n",
    "                for i in range(1, len(nums)):\n",
    "                    if nums[i]%2 !=0 and nums[i] > nums[i-1]:\n",
    "                        continue\n",
    "                    else:\n",
    "                        return False\n",
    "                return True\n",
    "            else:\n",
    "                if nums[0]%2 != 0:\n",
    "                    return False\n",
    "                for i in range(1, len(nums)):\n",
    "                    if nums[i]%2 ==0 and nums[i] < nums[i-1]:\n",
    "                        continue\n",
    "                    else:\n",
    "                        return False\n",
    "                return True\n",
    "        while q:\n",
    "            nums = []\n",
    "            for _ in range(len(q)):\n",
    "                cur = q.pop(0)\n",
    "                nums.append(cur.val)\n",
    "                if cur.left:\n",
    "                    q.append(cur.left)\n",
    "                if cur.right:\n",
    "                    q.append(cur.right)\n",
    "            if not check(nums, level):\n",
    "                return False\n",
    "            level += 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root :\n",
    "            return True\n",
    "        if root.val % 2==0:\n",
    "            return False\n",
    "        queue=[root]\n",
    "        result=0\n",
    "        level=1\n",
    "        while queue:\n",
    "            temp=[]\n",
    "            level*=-1\n",
    "            temp_var=-inf\n",
    "            for q in queue:\n",
    "                if q.left:\n",
    "                    if q.left.val*level<=temp_var or q.left.val % 2==(-0.5*level+0.5):\n",
    "                        return False\n",
    "                    temp_var=q.left.val*level\n",
    "                    temp.append(q.left)\n",
    "                if q.right:\n",
    "                    if q.right.val*level<=temp_var or q.right.val % 2==(-0.5*level+0.5):\n",
    "                        return False\n",
    "                    temp_var=q.right.val*level\n",
    "                    temp.append(q.right)\n",
    "            queue=temp\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # 层序遍历\n",
    "        now_level = 0 # 当前的层数\n",
    "        q=[root] # 当前的层有的元素\n",
    "        while len(q)>0:\n",
    "            # 遍历这一层的所有元素，先将这一层搬空\n",
    "            temp_node = q.copy()\n",
    "            q = []\n",
    "            pre_num=None\n",
    "            for node in temp_node:\n",
    "                if now_level%2==0:\n",
    "                    # 当前是偶数层，需要所有节点的值为奇数\n",
    "                    if node.val%2!=1:\n",
    "                        return False\n",
    "                    # 需要递增\n",
    "                    if pre_num==None:\n",
    "                        pre_num=node.val\n",
    "                    else:\n",
    "                        if node.val<=pre_num:\n",
    "                            return False\n",
    "                else:\n",
    "                    # 当前是奇数层，需要所有节点的值为偶数\n",
    "                    if node.val%2!=0:\n",
    "                        return False\n",
    "                    # 需要递减少\n",
    "                    if pre_num==None:\n",
    "                        pre_num=node.val\n",
    "                    else:\n",
    "                        if node.val>=pre_num:\n",
    "                            return False\n",
    "                # 更新上个节点的值\n",
    "                pre_num = node.val\n",
    "                # 将节点的左右子树加入队列\n",
    "                if node.left!=None:\n",
    "                    q.append(node.left)\n",
    "                if node.right!=None:\n",
    "                    q.append(node.right)\n",
    "            # 层数加1\n",
    "            now_level+=1\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # even depth: odd, left < right\n",
    "        # odd depth: even, left > right\n",
    "        depth = 0\n",
    "        q = [root]\n",
    "        while q:\n",
    "            tmp = []\n",
    "            n = len(q)\n",
    "            if depth % 2 == 0:\n",
    "                for i in range(n):\n",
    "                    if q[i].val % 2 == 0 or (i != 0 and q[i].val <= q[i-1].val):\n",
    "                        return False\n",
    "                    if q[i].left: tmp.append(q[i].left)\n",
    "                    if q[i].right: tmp.append(q[i].right)\n",
    "            else:\n",
    "                for i in range(n):\n",
    "                    if q[i].val % 2 == 1 or (i != 0 and q[i].val >= q[i-1].val):\n",
    "                        return False\n",
    "                    if q[i].left: tmp.append(q[i].left)\n",
    "                    if q[i].right: tmp.append(q[i].right)\n",
    "            depth += 1\n",
    "            q = tmp[:]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isIncrease(self, nums):\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] <= nums[i - 1]:\n",
    "                return False\n",
    "        return True\n",
    "    def isDecrease(self, nums):\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] >= nums[i - 1]:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # \n",
    "        # 偶数层，节点为奇数，节点严格递增\n",
    "        # 奇数层，节点为偶数，节点严格递减\n",
    "        # 即：层数 + 该层的任意节点数值均为奇数\n",
    "\n",
    "\n",
    "        queue = [root]\n",
    "        depth = 0\n",
    "\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            level = []\n",
    "\n",
    "            for _ in range(size):\n",
    "                node = queue.pop(0)\n",
    "                if (depth + node.val) % 2 == 0:\n",
    "                    return False\n",
    "                level.append(node.val)\n",
    "\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            print(level)\n",
    "            if depth % 2: # 奇数\n",
    "                if not self.isDecrease(level):\n",
    "                    return False\n",
    "            else: # 偶数\n",
    "                if not self.isIncrease(level):\n",
    "                    return False\n",
    "            depth += 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "\n",
    "        queue = [root]\n",
    "        even = True\n",
    "\n",
    "        while queue:\n",
    "            sz = len(queue)\n",
    "            prev = float('-inf') if even else float('inf')\n",
    "            for i in range(sz):\n",
    "                cur_node = queue.pop(0)\n",
    "\n",
    "                if even:\n",
    "                    if cur_node.val <= prev or cur_node.val % 2 != 1:\n",
    "                        return False\n",
    "                else:\n",
    "                    if cur_node.val >= prev or cur_node.val % 2 != 0:\n",
    "                        return False\n",
    "\n",
    "                if cur_node.left:\n",
    "                    queue.append(cur_node.left)\n",
    "                \n",
    "                if cur_node.right:\n",
    "                    queue.append(cur_node.right)\n",
    "                \n",
    "                prev = cur_node.val\n",
    "            \n",
    "            even = not even\n",
    "        \n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        layer_node=[root]\n",
    "        layer_index=0\n",
    "        even = True\n",
    "        odd = False\n",
    "\n",
    "        while layer_node!=[]:\n",
    "            layer_width=len(layer_node)\n",
    "            if even:\n",
    "                prev=0\n",
    "            else: prev=1000001\n",
    "\n",
    "            for i in range(layer_width):\n",
    "                curr = layer_node[0]\n",
    "                if curr.val%2==1 and curr.val<=prev:\n",
    "                    return False\n",
    "                if curr.val%2==0 and curr.val>=prev:\n",
    "                    return False\n",
    "\n",
    "                layer_node.pop(0)\n",
    "                if curr.left!=None:\n",
    "                    layer_node.append(curr.left)\n",
    "                if curr.right!=None:\n",
    "                    layer_node.append(curr.right)\n",
    "                prev = curr.val\n",
    "\n",
    "            even = not even\n",
    "            odd = not odd\n",
    "        return True\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        q = [root]\n",
    "\n",
    "        level = 0\n",
    "\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            if level % 2 == 0:\n",
    "                pre = 0\n",
    "                for _ in range(size):\n",
    "                    cur = q.pop(0)\n",
    "                    if cur.val % 2 != 1 or cur.val <= pre:\n",
    "                        return False\n",
    "                    if cur.left: q.append(cur.left)\n",
    "                    if cur.right: q.append(cur.right)\n",
    "                    pre = cur.val\n",
    "\n",
    "            else:\n",
    "                pre = q[0].val + 1\n",
    "                for _ in range(size):\n",
    "                    cur = q.pop(0)\n",
    "                    if cur.val % 2 != 0 or cur.val >= pre:\n",
    "                        return False \n",
    "                    if cur.left: q.append(cur.left)\n",
    "                    if cur.right: q.append(cur.right)\n",
    "                    pre = cur.val\n",
    "\n",
    "            level += 1\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "\n",
    "        queue = [root]\n",
    "        flag = True\n",
    "\n",
    "        while queue:\n",
    "            sz = len(queue)\n",
    "            for i in range(sz):\n",
    "                cur_node = queue.pop(0)\n",
    "\n",
    "                if i == 0:\n",
    "                    prev = cur_node.val\n",
    "                else:\n",
    "                    if flag:\n",
    "                        if cur_node.val <= prev:\n",
    "                            return False\n",
    "                    else:\n",
    "                        if cur_node.val >= prev:\n",
    "                            return False\n",
    "\n",
    "                if flag:\n",
    "                    if cur_node.val % 2 != 1:\n",
    "                        return False\n",
    "                else:\n",
    "                    if cur_node.val % 2 != 0:\n",
    "                        return False\n",
    "\n",
    "                if cur_node.left:\n",
    "                    queue.append(cur_node.left)\n",
    "                \n",
    "                if cur_node.right:\n",
    "                    queue.append(cur_node.right)\n",
    "                \n",
    "                prev = cur_node.val\n",
    "            \n",
    "            flag = not flag\n",
    "        \n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "\n",
    "        queue = [root]\n",
    "        flag = True\n",
    "\n",
    "        while queue:\n",
    "            sz = len(queue)\n",
    "            for i in range(sz):\n",
    "                cur_node = queue.pop(0)\n",
    "\n",
    "                if i > 0:\n",
    "                    if flag:\n",
    "                        if cur_node.val <= prev:\n",
    "                            return False\n",
    "                    else:\n",
    "                        if cur_node.val >= prev:\n",
    "                            return False\n",
    "\n",
    "                if flag:\n",
    "                    if cur_node.val % 2 != 1:\n",
    "                        return False\n",
    "                else:\n",
    "                    if cur_node.val % 2 != 0:\n",
    "                        return False\n",
    "\n",
    "                if cur_node.left:\n",
    "                    queue.append(cur_node.left)\n",
    "                \n",
    "                if cur_node.right:\n",
    "                    queue.append(cur_node.right)\n",
    "                \n",
    "                prev = cur_node.val\n",
    "            \n",
    "            flag = not flag\n",
    "        \n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        \n",
    "        queue = [root]\n",
    "        level = 0  # 根节点为0层\n",
    "        \n",
    "        while queue:\n",
    "            level_length = len(queue)\n",
    "            prev_value = -1 if level % 2 == 0 else float('inf')  # 初始化前一个节点的值\n",
    "\n",
    "            for i in range(level_length):\n",
    "                node = queue.pop(0)\n",
    "                # 判断当前层的节点值是否满足奇偶性要求\n",
    "                if level % 2 == 0 and (node.val % 2 == 0 or node.val <= prev_value):\n",
    "                    return False\n",
    "                if level % 2 == 1 and (node.val % 2 == 1 or node.val >= prev_value):\n",
    "                    return False\n",
    "                \n",
    "                prev_value = node.val\n",
    "                \n",
    "                # 添加子节点到队列中以便进行下一层的遍历\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            \n",
    "            level += 1  # 切换到下一层\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        layer_node=[root]\n",
    "        layer_index=0\n",
    "        even = True\n",
    "        #odd = False\n",
    "\n",
    "        while layer_node!=[]:\n",
    "            layer_width=len(layer_node)\n",
    "            if even:\n",
    "                prev=0\n",
    "            else: prev=1000001\n",
    "\n",
    "            for i in range(layer_width):\n",
    "                curr = layer_node[0]\n",
    "                if curr.val%2==1 and curr.val<=prev:#first curr.val<=prev只有prev=1000001才会成立，奇数层\n",
    "                    return False\n",
    "                if curr.val%2==0 and curr.val>=prev:\n",
    "                    return False\n",
    "\n",
    "                layer_node.pop(0)\n",
    "                if curr.left!=None:\n",
    "                    layer_node.append(curr.left)\n",
    "                if curr.right!=None:\n",
    "                    layer_node.append(curr.right)\n",
    "                prev = curr.val\n",
    "\n",
    "            even = not even\n",
    "            #odd = not odd\n",
    "        return True\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        \n",
    "        queue = [root]\n",
    "        level = 0  # 根节点为0层\n",
    "        \n",
    "        while queue:\n",
    "            level_length = len(queue)\n",
    "            prev_value = -1 if level % 2 == 0 else float('inf')  # 初始化前一个节点的值\n",
    "\n",
    "            for i in range(level_length):\n",
    "                node = queue.pop(0)\n",
    "                # 判断当前层的节点值是否满足奇偶性要求\n",
    "                if level % 2 == 0 and (node.val % 2 == 0 or node.val <= prev_value):\n",
    "                    return False\n",
    "                if level % 2 == 1 and (node.val % 2 == 1 or node.val >= prev_value):\n",
    "                    return False\n",
    "                \n",
    "                prev_value = node.val\n",
    "                \n",
    "                # 添加子节点到队列中以便进行下一层的遍历\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            \n",
    "            level += 1  # 切换到下一层\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "        q = [(root, 0)]\n",
    "        lvlist = []\n",
    "        while q:\n",
    "            node, lv = q.pop(0)\n",
    "            if lv >= len(lvlist):\n",
    "                lvlist.append([])\n",
    "            lvlist[lv].append(node.val)\n",
    "            if node.left:\n",
    "                q.append((node.left, lv+1))\n",
    "            if node.right:\n",
    "                q.append((node.right, lv+1))\n",
    "        # print(lvlist)\n",
    "        for i in range(len(lvlist)):\n",
    "            if i % 2 == 0:\n",
    "                if lvlist[i][0] % 2 == 0:\n",
    "                    return False\n",
    "            else:\n",
    "                if lvlist[i][0] % 2 == 1:\n",
    "                    return False\n",
    "            for j in range(1, len(lvlist[i])):\n",
    "                is_val_even = lvlist[i][j] % 2 == 0\n",
    "                if i % 2 == 0:\n",
    "                    if is_val_even or lvlist[i][j]<=lvlist[i][j-1]:\n",
    "                        return False\n",
    "                else:\n",
    "                    if not is_val_even or lvlist[i][j]>=lvlist[i][j-1]:\n",
    "                        return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: TreeNode) -> bool:\n",
    "        is_odd, queue = 0, [root]\n",
    "        while len(queue):\n",
    "            nodes_nums = len(queue)\n",
    "            pre = float('inf') if is_odd else float('-inf')\n",
    "            for _ in range(nodes_nums):\n",
    "                node = queue.pop(0)\n",
    "                if node is None:\n",
    "                    continue\n",
    "                q1 = node.val & 1 == is_odd  # 判断是否符合奇偶性\n",
    "                q2 = is_odd and node.val >= pre  # 判断奇数层是否严格递减\n",
    "                q3 = not is_odd and node.val <= pre  # 判断奇数层是否严格递增\n",
    "                if q1 or q2 or q3:\n",
    "                    return False\n",
    "                pre = node.val\n",
    "                queue += [node.left, node.right]\n",
    "            is_odd ^= 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        from queue import Queue\n",
    "        q = Queue()\n",
    "        if root is None:\n",
    "            return True\n",
    "        level = 0\n",
    "        q.put(root)\n",
    "        while q:\n",
    "            sz = q.qsize()\n",
    "            tmp = []\n",
    "            before_value = None\n",
    "            for _ in range(sz):\n",
    "                curr = q.get()\n",
    "                tmp.append(curr.val)\n",
    "                curr_value = curr.val\n",
    "                if level % 2 == 0:\n",
    "                    if curr_value % 2 == 0:\n",
    "                        return False\n",
    "                    if before_value is not None and curr_value <= before_value:\n",
    "                        return False\n",
    "                else:\n",
    "                    if curr_value % 2 != 0:\n",
    "                        return False\n",
    "                    if before_value is not None and curr_value >= before_value:\n",
    "                        return False\n",
    "                before_value = curr_value\n",
    "                if curr.left:\n",
    "                    q.put(curr.left)\n",
    "                if curr.right:\n",
    "                    q.put(curr.right)\n",
    "            if sz == 0:\n",
    "                break\n",
    "            else:\n",
    "                level += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "\n",
    "        queue = []\n",
    "        queue.append(root)\n",
    "        flag = 1\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            pre = 0\n",
    "            for i in range(size):\n",
    "                node = queue.pop(0)\n",
    "\n",
    "                if flag > 0 and node.val % 2 == 0:\n",
    "                    return False\n",
    "                \n",
    "                if flag < 0 and node.val % 2 != 0:\n",
    "                    return False\n",
    "                \n",
    "                if pre == 0:\n",
    "                    pre = node.val\n",
    "                else:\n",
    "                    if pre * flag < node.val * flag:\n",
    "                        pre = node.val\n",
    "                    else:\n",
    "                        return False\n",
    "\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                \n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            \n",
    "            flag = -flag\n",
    "        \n",
    "\n",
    "        return True\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        \n",
    "        stack = [root] if root else []\n",
    "        row = 0\n",
    "        while stack:\n",
    "            lst = [node.val for node in stack]\n",
    "            if row == 0:\n",
    "                if not (all(x%2==1 for x in lst) and sorted(lst)==lst and len(lst)==len(set(lst))):\n",
    "                    return False\n",
    "            else:\n",
    "                if not (all(x%2==0 for x in lst) and sorted(lst)==lst[::-1] and len(lst)==len(set(lst))):\n",
    "                    return False\n",
    "            nex = []\n",
    "            for node in stack:\n",
    "                if node.left:\n",
    "                    nex.append(node.left)\n",
    "                if node.right:\n",
    "                    nex.append(node.right)\n",
    "            stack = nex[:]\n",
    "            row = 1-row\n",
    "        return True\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        stack = deque()\n",
    "        stack.append(root)\n",
    "        high = 1\n",
    "        while stack:\n",
    "            ans = []\n",
    "            for _ in range(len(stack)):\n",
    "                t = stack.popleft()\n",
    "                if high % 2 == 1:\n",
    "                    if t.val % 2 == 1:\n",
    "                        if ans and ans[-1] >= t.val:\n",
    "                            return False\n",
    "                    else:\n",
    "                        return False\n",
    "                else:\n",
    "                    if t.val % 2 == 0 :\n",
    "                        if ans and ans[-1] <= t.val:\n",
    "                            return False\n",
    "                    else:\n",
    "                        return False\n",
    "                ans.append(t.val)\n",
    "                if t.left:\n",
    "                    stack.append(t.left)\n",
    "                if t.right:\n",
    "                    stack.append(t.right)\n",
    "            high += 1\n",
    "        return True\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def asc(arr):\n",
    "            for i in range(len(arr)-1):\n",
    "                if arr[i+1] <= arr[i]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        def desc(arr):\n",
    "            for i in range(len(arr)-1):\n",
    "                if arr[i+1] >= arr[i]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        def bfs(root):\n",
    "            if not root:\n",
    "                return []\n",
    "            queue = deque([root])\n",
    "            res = []\n",
    "            while queue:\n",
    "                tmp = []\n",
    "                size = len(queue)\n",
    "                for i in range(size):\n",
    "                    node = queue.popleft()\n",
    "                    tmp.append(node.val)\n",
    "                    if node.left:\n",
    "                        queue.append(node.left)\n",
    "                    if node.right:\n",
    "                        queue.append(node.right)\n",
    "                res.append(tmp)\n",
    "            return res\n",
    "\n",
    "        res = bfs(root)\n",
    "        for idx, val in enumerate(res):\n",
    "            if idx % 2 == 0:\n",
    "                if not all(i % 2 == 1 for i in val) or not asc(val):\n",
    "                    return False \n",
    "            else:\n",
    "                if not all(i % 2 == 0 for i in val) or not desc(val):\n",
    "                    return False \n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.val % 2 ==0:\n",
    "            return False\n",
    "        q = collections.deque()\n",
    "        q.append((root,0))\n",
    "        pre = collections.defaultdict(lambda:None)\n",
    "        while q:\n",
    "            curnode,curlevel = q.popleft()\n",
    "            curlevel += 1\n",
    "            if curnode.left:\n",
    "                node = curnode.left\n",
    "                if (node.val + curlevel) %2 != 0:\n",
    "                    if not pre[curlevel] or (curlevel % 2 != 0 and node.val < pre[curlevel]) or (curlevel % 2 == 0 and node.val > pre[curlevel]) :\n",
    "                        pre[curlevel] = node.val\n",
    "                        q.append((node,curlevel))\n",
    "                    else:\n",
    "                        return False\n",
    "                else:\n",
    "                    return False\n",
    "            if curnode.right:\n",
    "                node = curnode.right\n",
    "                if (node.val + curlevel)%2 != 0:\n",
    "                    if not pre[curlevel] or (curlevel % 2 != 0 and node.val < pre[curlevel]) or (curlevel % 2 == 0 and node.val > pre[curlevel]) :\n",
    "                        pre[curlevel] = node.val\n",
    "                        q.append((node,curlevel))\n",
    "                    else:\n",
    "                        return False\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.val % 2 ==0:\n",
    "            return False\n",
    "        q = collections.deque()\n",
    "        q.append((root,0))\n",
    "        pre = collections.defaultdict(lambda:None)\n",
    "        while q:\n",
    "            curnode,curlevel = q.popleft()\n",
    "            curlevel += 1\n",
    "            if curnode.left:\n",
    "                node = curnode.left\n",
    "                if (node.val + curlevel) %2 != 0:\n",
    "                    if not pre[curlevel] or (curlevel % 2 != 0 and node.val < pre[curlevel]) or (curlevel % 2 == 0 and node.val > pre[curlevel]) :\n",
    "                        pre[curlevel] = node.val\n",
    "                        q.append((node,curlevel))\n",
    "                    else:\n",
    "                        return False\n",
    "                else:\n",
    "                    return False\n",
    "            if curnode.right:\n",
    "                node = curnode.right\n",
    "                if (node.val + curlevel)%2 != 0:\n",
    "                    if not pre[curlevel] or (curlevel % 2 != 0 and node.val < pre[curlevel]) or (curlevel % 2 == 0 and node.val > pre[curlevel]) :\n",
    "                        pre[curlevel] = node.val\n",
    "                        q.append((node,curlevel))\n",
    "                    else:\n",
    "                        return False\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.val%2==0:\n",
    "            return False\n",
    "        def isup(nums):\n",
    "            if not nums:\n",
    "                return True\n",
    "            l = nums[0]\n",
    "            if l.val %2 == 0:\n",
    "                return False\n",
    "            for i in nums[1:]:\n",
    "                if i.val %2 ==0:\n",
    "                    return False\n",
    "                if l.val >= i.val:\n",
    "                    return False\n",
    "                l = i\n",
    "            return True\n",
    "        def isdown(nums):\n",
    "            if not nums:\n",
    "                return True\n",
    "            l = nums[0]\n",
    "            if l.val%2==1:\n",
    "                return False\n",
    "            for i in nums[1:]:\n",
    "                if i.val%2==1:\n",
    "                    return False\n",
    "                if l.val <= i.val:\n",
    "                    return False\n",
    "                l = i\n",
    "            return True\n",
    "        \n",
    "        if not root:\n",
    "            return []\n",
    "        levelmap = {}\n",
    "        level = 0\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            stack = []\n",
    "            if level >=1:\n",
    "                if level %2 ==0:\n",
    "                    if not isup(queue):\n",
    "                        return False\n",
    "                else:\n",
    "                    if not isdown(queue):\n",
    "                        return False\n",
    "            while queue:\n",
    "                stack.append(queue.pop(0))\n",
    "            while stack:\n",
    "                node = stack.pop(0)\n",
    "                if level not in levelmap.keys():\n",
    "                    levelmap[level] = []\n",
    "                levelmap[level].append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            level += 1\n",
    "        # 校验\n",
    "        print(levelmap)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        pre=[]\n",
    "        def dfs(node,depth):\n",
    "            if node==None:\n",
    "                return True\n",
    "            val=node.val\n",
    "            if val%2!=(depth+1)%2:\n",
    "                return False\n",
    "            if depth == len(pre):\n",
    "                pre.append(node.val)\n",
    "            else:\n",
    "                if depth%2==0:\n",
    "                    if pre[depth]>=val:\n",
    "                        return False\n",
    "                else:\n",
    "                    if pre[depth]<=val:\n",
    "                        return False\n",
    "                pre[depth]=val\n",
    "            return dfs(node.left,depth+1) and dfs(node.right,depth+1)\n",
    "        return dfs(root,0)\n",
    "              "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        flag = []\n",
    "        def dfs(node, depth, odd):\n",
    "            if node is None: return True \n",
    "\n",
    "            if depth == len(flag):\n",
    "                flag.append(node)\n",
    "                if odd and node.val % 2 == 1: return False\n",
    "                if not odd and node.val % 2 == 0: return False\n",
    "            else:\n",
    "                if odd:\n",
    "                    if node.val % 2 == 1 or node.val >= flag[depth].val: return False\n",
    "                else:\n",
    "                    if node.val % 2 == 0 or node.val <= flag[depth].val: return False\n",
    "                flag[depth] = node\n",
    "\n",
    "            return dfs(node.left, depth+1, not odd) and dfs(node.right, depth+1, not odd)\n",
    "\n",
    "        return dfs(root, 0, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        array = []\n",
    "\n",
    "        def dfs(root, depth):\n",
    "            if(not root):\n",
    "                return\n",
    "            if(len(array)<=depth):\n",
    "                array.append([])\n",
    "            dfs(root.left, depth+1)\n",
    "            array[depth].append(root.val)\n",
    "            dfs(root.right,depth+1)\n",
    "        \n",
    "        dfs(root, 0)\n",
    "\n",
    "        for i in range(len(array)):\n",
    "            if( i % 2 == 0):\n",
    "                tem1 = array[i][0]\n",
    "                if(tem1 % 2 == 0):\n",
    "                    return False\n",
    "                for j in range(1,len(array[i])):\n",
    "                    if(array[i][j] % 2 == 0):\n",
    "                        return False\n",
    "                    if( array[i][j] <= array[i][j-1]):\n",
    "                        return False\n",
    "            else:\n",
    "                tem1 = array[i][-1]\n",
    "                if(tem1 % 2 == 1):\n",
    "                    return False\n",
    "                for j in range(len(array[i])-2,-1,-1):\n",
    "                    if(j >= 0):\n",
    "                        if( array[i][j] <= array[i][j+1]):\n",
    "                            return False\n",
    "                \n",
    "        return True\n",
    "\n",
    "        print(array)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def bfs(nodes, odd):\n",
    "            if odd:\n",
    "                for i in range(1, len(nodes)):\n",
    "                    if nodes[i-1].val<=nodes[i].val:\n",
    "                        return False\n",
    "            else:\n",
    "                for i in range(1, len(nodes)):\n",
    "                    if nodes[i-1].val>=nodes[i].val:\n",
    "                        return False\n",
    "            next_nodes = []\n",
    "            for node in nodes:\n",
    "                if odd and (node.val)%2==1:\n",
    "                    return False\n",
    "                if not odd and (node.val)%2==0:\n",
    "                    return False\n",
    "                if node.left:\n",
    "                    next_nodes.append(node.left)\n",
    "                if node.right:\n",
    "                    next_nodes.append(node.right)\n",
    "            if next_nodes:\n",
    "                return bfs(next_nodes, not odd)\n",
    "        ret = bfs([root], False)\n",
    "        return ret is None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        ##尝试方法：  层序输出每一层，配上层值信息； check\n",
    "        ##下面这个方法，来自 102. 二叉树的层序遍历\n",
    "        res = []\n",
    "        def bfs(node, lv):\n",
    "            if not node:\n",
    "                return\n",
    "            if len(res)< lv+1:    res.append([])    ##智能添加维度\n",
    "            res[lv].append(node.val)\n",
    "            bfs(node.left, lv+1)\n",
    "            bfs(node.right, lv+1)\n",
    "\n",
    "        def check(i, line):\n",
    "            if i % 2 == 0:\n",
    "                for x in line:\n",
    "                    if x % 2 == 0: return 1\n",
    "                for x, y in pairwise(line):\n",
    "                    if x>=y:    return 1\n",
    "            else:\n",
    "                for x in line:\n",
    "                    if x % 2 == 1: return 1\n",
    "                for x, y in pairwise(line):\n",
    "                    if x<= y:   return 1\n",
    "\n",
    "        bfs(root, 0)\n",
    "        for i, x in enumerate(res):\n",
    "            if check(i, x):\n",
    "                return False\n",
    "        return True\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
